// 题目描述：给你一个字符串 s，找到 s 中最长的回文子串

function longestPalindrome(s) {
    if (s.length === 1) return s;

    // 创建二阶数组存储从j到i是否是回文数组， 0为不回文，1为回文
    let arr = []; 
    for (let i = 0; i < s.length; i++) {
        arr[i] = [];
    };

    // 存储最长回文子串的起始位置
    let start = 0;
    // 存储最长子串的长度
    let max = 0;

    for (let i = 0 ; i < s.length; i++) {
        let j = 0;
        while (j <= i) {
            // 如果i-j <= 1时，说明i位置和j位置要么是重合的，要么是相邻的，即为最后一次查找
            // 否则继续查询[j+1]到[i-1]是否为回文
            if (s[j] == s[i] && (i - j <= 1 || arr[j+1][i-1])) {
                // 如果符合上述条件，说明j到i回文
                arr[j][i] = 1;

                if (i - j + 1 > max) {
                    start = j;
                    max = i - j + 1;
                }
            };
            j++;
        };
    };

    return s.substr(start,max);
};



// test

const s = "babad";
console.log(longestPalindrome(s));
